The present invention relates generally to autonomous systems, and more particularly to discovering network paths in autonomous systems.
An autonomous system (AS) is a collection of networks (i.e., the routers joining those networks) under the same administrative authority and that share a common routing strategy. The Internet includes over 20,000 inter-connected ASes controlled by different administrative domains such as Internet Service Providers (ISPs), corporations, universities, and research institutions.
Different ASes interact with each other in a complex manner through the use of a Border Gateway Protocol (BGP), which is a protocol for exchanging routing information between nodes (e.g., routers). BGP enables each individual administrative domain to specify its own routing policies.
The enormous scale and highly heterogeneous and uncooperative nature of the Internet have made it a major challenge for today's network operators to understand routing protocol behavior and detect and diagnose problems. In particular, discovering paths in a network provides valuable information for network operators. Network operators can detect and diagnose problems, study routing protocol behavior, characterize end-to-end paths through the Internet, and better understand network performance when network paths are discovered.
There are several currently available tools and techniques that network operators use for path discovery. For example, traceroute is a utility that traces a packet from a source node (e.g., a user's computer) to an Internet host. Traceroute shows how many hops the packet requires to reach the host and its duration. A user can therefore determine where the longest delays are occurring if the user is visiting a web site and web pages are appearing slowly. Traceroute utilities work by sending packets with low time-to-live (TTL) fields from the source node. The TTL value specifies how many hops the packet is allowed before it is returned. When a packet cannot reach its destination because the TTL value is too low, the last host returns the packet and identifies itself. By sending a series of packets and incrementing the TTL value with each successive packet, traceroute identifies the intermediary hosts.
Another technique used to determine network paths is by obtaining a Border Gateway Protocol (BGP) table. As each node within a network has a BGP routing table denoting the network devices that the node communicates with, obtaining a source's BGP routing table will enable a network operator to determine the path that packets take from the source node.
In both the BGP routing table technique and the traceroute technique, however, a network operator must have direct access to the source node to discover a network path. In particular, the traceroute utility requires packets to be sent from the source node to determine the path that they take. Similarly, when a network operator determines a path using a BGP table, the network operator has to obtain the BGP table from the source node to determine the complete path taken by the packets.
Unfortunately, in today's Internet, asymmetric routing is commonly used. Asymmetric routing is when the path from node n1 to node n2 is different than the path from node n2 to node n1. Asymmetric routing may occur, for example, because of policy-based interdomain routing (i.e., routing policies that selectively cause packets to take different paths). As a result, when a network operator only has access to a source node, determining the path in the reverse direction (i.e., from the destination node to the source node) is virtually impossible. The problem becomes even more challenging when direct access to the source and destination nodes are unavailable.